/*
 * @lc app=leetcode.cn id=707 lang=java
 * @lcpr version=30201
 *
 * [707] 设计链表
 */

// @lc code=start
class MyLinkedList {
    final ListNode head,tail;
    int size;
    private static class ListNode {
        int val;
        ListNode prev;
        ListNode next;

        ListNode(int val){
            this.val=val;
        }
    }
    
    public MyLinkedList(){
        head=new ListNode(0);
        tail=new ListNode(0);
        head.next=tail;
        tail.prev=head;
        size=0;
    }

    public int get(int index) {
        if(index>=size) return -1;
        else {
            ListNode p=head.next;
            while(index--!=0){
                p=p.next;
            }
            return p.val;
        }
    }
    
    public void addAtHead(int val) {
        ListNode p=new ListNode(val);
        p.prev=head;
        p.next=head.next;
        p.next.prev=p;
        head.next=p;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode p=new ListNode(val);
        p.next=tail;
        p.prev=tail.prev;
        p.prev.next=p;
        tail.prev=p;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size) return;
        else if(index==size){
            addAtTail(val);
            return;
        }
        else{
            ListNode p=new ListNode(val);
            ListNode cur=head.next;
            while(index--!=0){
                cur=cur.next;
            }
            p.prev=cur.prev;
            p.next=cur;
            p.prev.next=p;
            cur.prev=p;
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        if(index>=size) return;
        else{
            ListNode p=head.next;
            while (index--!=0) {
                p=p.next;
            }
            p.prev.next=p.next;
            p.next.prev=p.prev;
            size--;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
// @lc code=end



